home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_12_08 / treu / flood.c < prev    next >
C/C++ Source or Header  |  1994-04-25  |  6KB  |  263 lines
  1. /******************************************************
  2.  * FLOOD.C - optimized flood visit
  3.  *
  4.  * This algorithm visits once each all 4-way connected
  5.  * interior points on a finite plane which share a 
  6.  * common property, given a starting point which has 
  7.  * the property and a function which can determine 
  8.  * whether any given point also has it.  The common 
  9.  * points need not form a convex region, that is, 
  10.  * islands and peninsulas bounded by points which do 
  11.  * not share the common property may exist within the
  12.  * region of points which do.
  13.  *
  14.  * for ANSI C
  15.  *
  16.  * by Anton Treuenfels
  17.  * last revision:  04/12/94
  18.  *
  19.  * references:
  20.  * Lieberman, Henry, "How To Color In A Coloring Book",
  21.  *   in Computer Graphics, Vol. 12, No. 3, Aug 1978
  22.  * Polik, William F., "Area Filling Algorithms",
  23.  *   in Computer Language, Vol. 3, No. 5, May 1986
  24.  * Wilton, Richard, "PC & PS/2 Video Systems",
  25.  *   Microsoft Press, 1987
  26.  *****************************************************/
  27.  
  28. /****************************
  29.  * HEADER SECTION - FLOOD.H *
  30.  ****************************/
  31.  
  32. #ifndef SEEN_FLOOD
  33. #define SEEN_FLOOD
  34.  
  35. /* function prototype */
  36.  
  37. int flood(int, int, int (*)(int, int));
  38.  
  39. #endif
  40.  
  41. /**************************
  42.  * CODE SECTION - FLOOD.C *
  43.  **************************/
  44.  
  45. #include <stdlib.h>
  46. #include <setjmp.h>
  47.  
  48. #include "usrdef.h"
  49.  
  50. /* line shadow */
  51.  
  52. typedef struct shdw {
  53.     struct shdw *next;      /* forward link */
  54.     int lft, rgt;           /* endpoints */
  55.     int row, par;           /* row and parent row */
  56.     Boolean ok;             /* valid flag */
  57. } shadow;
  58.  
  59. /* shadow variables */
  60.  
  61. static int currRow;         /* current row */
  62. static shadow *seedShadow;  /* current shadow */
  63. static shadow *rowHead;     /* current row shadows */
  64. static shadow *pendHead;    /* other pending shadows */
  65. static shadow *freeHead;    /* unused shadow nodes */
  66.  
  67. /* visit coordinate function */
  68.  
  69. static int (*isInterior)(int, int);
  70.  
  71. /* error recovery buffer */
  72.  
  73. static jmp_buf errBuf;
  74.  
  75. /*****************************************************/
  76.  
  77. /* release shadow nodes */
  78.  
  79. static void freeshadows(shadow *s) {
  80.  
  81.     shadow *t;
  82.  
  83.     while (s) {
  84.         t = s->next;
  85.         free(s);
  86.         s = t;
  87.     }
  88. }
  89.  
  90. /* make new shadow */
  91.  
  92. static void newshadow(int slft, int srgt,
  93.         int srow, int prow) {
  94.  
  95.     shadow *new;
  96.  
  97.     if ((new = freeHead) != NULL)
  98.         freeHead = freeHead->next;
  99.     else if ((new = malloc(sizeof(shadow))) == NULL) {
  100.         freeshadows(rowHead);
  101.         freeshadows(pendHead);
  102.         longjmp(errBuf, !0);
  103.     }
  104.  
  105.     new->lft = slft;  new->rgt = srgt;
  106.     new->row = srow;  new->par = prow;
  107.     new->ok = TRUE;
  108.     new->next = pendHead;
  109.     pendHead = new;
  110. }
  111.  
  112. /* make list of all shadows on one row */
  113.  
  114. static void makerow(void) {
  115.  
  116.     shadow *s, *t, *u;
  117.  
  118.     t = pendHead;
  119.     pendHead = NULL;
  120.     while ((s = t) != NULL) {
  121.         t = t->next;
  122.         if (s->ok) {
  123.             if (rowHead == NULL) {
  124.                 currRow = s->row;
  125.                 s->next = NULL;
  126.                 rowHead = s;
  127.             }
  128.             else if (s->row == currRow) {
  129.                 if (s->lft <= rowHead->lft) {
  130.                     s->next = rowHead;
  131.                     rowHead = s;
  132.                 }
  133.                 else {
  134.                     for (u = rowHead; u->next; u = u->next)
  135.                         if (s->lft <= u->next->lft)
  136.                             break;
  137.                     s->next = u->next;
  138.                     u->next = s;
  139.                 }
  140.             }
  141.             else {
  142.                 s->next = pendHead;
  143.                 pendHead = s;
  144.             }
  145.         }
  146.         else {
  147.             s->next = freeHead;
  148.             freeHead = s;
  149.         }
  150.     }
  151. }
  152.  
  153. /* make new shadow(s) that don't overlap lines */
  154.  
  155. static void clipshadow(int lft, int rgt, int row,
  156.          shadow *line) {
  157.  
  158.     if (lft < (line->lft - 1))
  159.         newshadow(lft, line->lft - 2, row, line->row);
  160.     if (rgt > (line->rgt + 1))
  161.         newshadow(line->rgt + 2, rgt, row, line->row);
  162. }
  163.  
  164. /* discard shadow segments which overlap lines */
  165.  
  166. static void removeoverlap(shadow *rw) {
  167.  
  168.     shadow *chld;
  169.  
  170.     for (chld = pendHead; chld->row != rw->par;
  171.              chld = chld->next)
  172.         ;
  173.  
  174.     clipshadow(chld->lft, chld->rgt, chld->row, rw);
  175.     if (rw->rgt > (chld->rgt + 1))
  176.         rw->lft = chld->rgt + 2;
  177.     else
  178.         rw->ok = FALSE;
  179.     chld->ok = FALSE;
  180. }
  181.  
  182. /* make shadows of one child line */
  183.  
  184. static void makeshadows(int lft, int rgt) {
  185.  
  186.     shadow *p;
  187.  
  188.     if (currRow > seedShadow->par) {
  189.         newshadow(lft, rgt, currRow + 1, currRow);
  190.         clipshadow(lft, rgt, currRow - 1, seedShadow);
  191.     }
  192.     else if (currRow < seedShadow->par) {
  193.         newshadow(lft, rgt, currRow - 1, currRow);
  194.         clipshadow(lft, rgt, currRow + 1, seedShadow);
  195.     }
  196.     else {
  197.         newshadow(lft, rgt, currRow + 1, currRow);
  198.         newshadow(lft, rgt, currRow - 1, currRow);
  199.     }
  200.  
  201.     for (p = rowHead; p && (p->lft <= rgt); p = p->next)
  202.         if (p->ok)
  203.             removeoverlap(p);
  204. }
  205.  
  206. /* visit all child lines found within one shadow */
  207.  
  208. static void visitshadow(void) {
  209.  
  210.     int col, lft;
  211.  
  212.     for (col = seedShadow->lft; col <= seedShadow->rgt;
  213.              col++) {
  214.         if ((*isInterior)(col, currRow)) {
  215.             if ((lft = col) == seedShadow->lft) {
  216.                 while ((*isInterior)(--lft, currRow))
  217.                     ;
  218.                 lft++;
  219.             }
  220.             while ((*isInterior)(++col, currRow))
  221.                 ;
  222.  
  223.             makeshadows(lft, col - 1);
  224.         }
  225.     }
  226. }
  227.  
  228. /* flood visit */
  229.  
  230. static void doflood(int seedx, int seedy,
  231.              int (*visit)(int, int)) {
  232.  
  233.     isInterior = visit;
  234.     pendHead = rowHead = freeHead = NULL;
  235.     newshadow(seedx, seedx, seedy, seedy);
  236.     while (pendHead) {
  237.         makerow();
  238.         while (rowHead) {
  239.             seedShadow = rowHead;
  240.             rowHead = rowHead->next;
  241.             if (seedShadow->ok)
  242.                 visitshadow();
  243.             seedShadow->next = freeHead;
  244.             freeHead = seedShadow;
  245.         }
  246.     }
  247.     freeshadows(freeHead);
  248. }
  249.  
  250. /* execute flood visit through guard function */
  251.  
  252. int flood(int seedx, int seedy,
  253.          int (*visit)(int, int)) {
  254.  
  255.     if (setjmp(errBuf) != 0)
  256.         return(FAIL);
  257.     doflood(seedx, seedy, visit);
  258.     return(OK);
  259. }
  260.  
  261.  
  262.  
  263.